package com.zjcloud.jwgl.algorithm;

import com.zjcloud.jwgl.domain.AcLessonSchedule;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Component;

import java.util.*;
import java.util.concurrent.*;
import java.util.stream.Collectors;

/**
 * 优化版遗传算法排课引擎
 * 1. 引入并行计算
 * 2. 使用缓存优化
 * 3. 采用高效数据结构
 * 4. 实现自适应参数
 */
@Component
public class OptimizedGeneticScheduler {
    
    /** 线程池 */
    private final ExecutorService executorPool;
    
    /** Redis缓存 */
    private final RedisTemplate<String, Object> redisTemplate;
    
    /** 种群大小 */
    private int populationSize = 100;
    
    /** 最大迭代次数 */
    private int maxGenerations = 200;
    
    /** 自适应交叉概率 */
    private double crossoverRate = 0.8;
    
    /** 自适应变异概率 */
    private double mutationRate = 0.1;
    
    /** 精英保留比例 */
    private double eliteRate = 0.1;
    
    /** 冲突检测缓存 */
    private final Map<String, BitSet> timeSlotCache;
    
    /** 约束条件缓存 */
    private final Map<String, Object> constraintCache;
    
    public OptimizedGeneticScheduler(RedisTemplate<String, Object> redisTemplate) {
        this.redisTemplate = redisTemplate;
        this.executorPool = Executors.newFixedThreadPool(
            Runtime.getRuntime().availableProcessors()
        );
        this.timeSlotCache = new ConcurrentHashMap<>();
        this.constraintCache = new ConcurrentHashMap<>();
    }
    
    /**
     * 执行排课算法
     */
    public List<AcLessonSchedule> schedule(List<Long> courses, List<Long> teachers,
                                         List<Long> classrooms, List<Long> classes,
                                         Map<String, Object> constraints) {
        // 初始化缓存
        initializeCache(constraints);
        
        // 并行初始化种群
        List<List<AcLessonSchedule>> population = initializePopulationParallel(courses, teachers, classrooms, classes);
        
        // 迭代优化
        for (int generation = 0; generation < maxGenerations; generation++) {
            // 并行计算适应度
            Map<List<AcLessonSchedule>, Double> fitnessMap = evaluateFitnessParallel(population);
            
            // 动态调整参数
            adjustParameters(generation, fitnessMap);
            
            // 选择操作
            List<List<AcLessonSchedule>> selected = tournamentSelection(population, fitnessMap);
            
            // 并行执行交叉和变异
            List<List<AcLessonSchedule>> offspring = crossoverAndMutateParallel(selected);
            
            // 精英保留
            population = elitism(population, offspring, fitnessMap);
            
            // 检查终止条件
            if (checkTerminationCondition(fitnessMap)) {
                break;
            }
        }
        
        // 清理缓存
        clearCache();
        
        return getBestSolution(population);
    }
    
    /**
     * 并行初始化种群
     */
    private List<List<AcLessonSchedule>> initializePopulationParallel(List<Long> courses,
                                                                    List<Long> teachers,
                                                                    List<Long> classrooms,
                                                                    List<Long> classes) {
        List<Callable<List<AcLessonSchedule>>> tasks = new ArrayList<>();
        for (int i = 0; i < populationSize; i++) {
            tasks.add(() -> generateOptimizedChromosome(courses, teachers, classrooms, classes));
        }
        
        try {
            List<Future<List<AcLessonSchedule>>> futures = executorPool.invokeAll(tasks);
            return futures.stream()
                .map(future -> {
                    try {
                        return future.get();
                    } catch (Exception e) {
                        return new ArrayList<AcLessonSchedule>();
                    }
                })
                .collect(Collectors.toList());
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            return new ArrayList<>();
        }
    }
    
    /**
     * 生成优化的染色体
     */
    private List<AcLessonSchedule> generateOptimizedChromosome(List<Long> courses,
                                                            List<Long> teachers,
                                                            List<Long> classrooms,
                                                            List<Long> classes) {
        List<AcLessonSchedule> chromosome = new ArrayList<>();
        Random random = new Random();
        
        // 使用BitSet跟踪时间槽占用情况
        Map<String, BitSet> timeSlots = new HashMap<>();
        
        for (Long courseId : courses) {
            AcLessonSchedule schedule = new AcLessonSchedule();
            schedule.setCourseId(courseId);
            
            // 优化分配过程
            boolean allocated = false;
            while (!allocated) {
                Long teacherId = teachers.get(random.nextInt(teachers.size()));
                Long classroomId = classrooms.get(random.nextInt(classrooms.size()));
                Long classId = classes.get(random.nextInt(classes.size()));
                
                int weekDay = random.nextInt(5) + 1;
                int lessonNo = random.nextInt(12) + 1;
                
                // 检查时间槽是否可用
                if (isTimeSlotAvailableOptimized(timeSlots, teacherId, classroomId, classId, weekDay, lessonNo)) {
                    schedule.setTeacherId(teacherId);
                    schedule.setClassroomId(classroomId);
                    schedule.setClassId(classId);
                    schedule.setWeekDay(weekDay);
                    schedule.setLessonNo(lessonNo);
                    schedule.setStatus("0");
                    
                    // 更新时间槽占用
                    updateTimeSlots(timeSlots, teacherId, classroomId, classId, weekDay, lessonNo);
                    
                    allocated = true;
                }
            }
            
            chromosome.add(schedule);
        }
        
        return chromosome;
    }
    
    /**
     * 优化的时间槽检查
     */
    private boolean isTimeSlotAvailableOptimized(Map<String, BitSet> timeSlots,
                                               Long teacherId,
                                               Long classroomId,
                                               Long classId,
                                               int weekDay,
                                               int lessonNo) {
        int timeSlotIndex = (weekDay - 1) * 12 + (lessonNo - 1);
        
        // 检查教师时间冲突
        BitSet teacherSlots = timeSlots.computeIfAbsent("T" + teacherId, k -> new BitSet(60));
        if (teacherSlots.get(timeSlotIndex)) {
            return false;
        }
        
        // 检查教室时间冲突
        BitSet classroomSlots = timeSlots.computeIfAbsent("R" + classroomId, k -> new BitSet(60));
        if (classroomSlots.get(timeSlotIndex)) {
            return false;
        }
        
        // 检查班级时间冲突
        BitSet classSlots = timeSlots.computeIfAbsent("C" + classId, k -> new BitSet(60));
        return !classSlots.get(timeSlotIndex);
    }
    
    /**
     * 更新时间槽占用情况
     */
    private void updateTimeSlots(Map<String, BitSet> timeSlots,
                               Long teacherId,
                               Long classroomId,
                               Long classId,
                               int weekDay,
                               int lessonNo) {
        int timeSlotIndex = (weekDay - 1) * 12 + (lessonNo - 1);
        
        timeSlots.get("T" + teacherId).set(timeSlotIndex);
        timeSlots.get("R" + classroomId).set(timeSlotIndex);
        timeSlots.get("C" + classId).set(timeSlotIndex);
    }
    
    /**
     * 并行计算适应度
     */
    private Map<List<AcLessonSchedule>, Double> evaluateFitnessParallel(List<List<AcLessonSchedule>> population) {
        Map<List<AcLessonSchedule>, Double> fitnessMap = new ConcurrentHashMap<>();
        
        List<Callable<Void>> tasks = population.stream()
            .map(chromosome -> (Callable<Void>) () -> {
                double fitness = calculateFitnessOptimized(chromosome);
                fitnessMap.put(chromosome, fitness);
                return null;
            })
            .collect(Collectors.toList());
        
        try {
            executorPool.invokeAll(tasks);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
        
        return fitnessMap;
    }
    
    /**
     * 优化的适应度计算
     */
    private double calculateFitnessOptimized(List<AcLessonSchedule> chromosome) {
        String cacheKey = "fitness:" + chromosome.hashCode();
        Double cachedFitness = (Double) redisTemplate.opsForValue().get(cacheKey);
        
        if (cachedFitness != null) {
            return cachedFitness;
        }
        
        double fitness = 1000.0;
        
        // 使用BitSet优化冲突检测
        Map<String, BitSet> conflicts = new HashMap<>();
        
        for (AcLessonSchedule schedule : chromosome) {
            int timeSlotIndex = (schedule.getWeekDay() - 1) * 12 + (schedule.getLessonNo() - 1);
            
            // 检查并记录冲突
            String teacherKey = "T" + schedule.getTeacherId();
            String classroomKey = "R" + schedule.getClassroomId();
            String classKey = "C" + schedule.getClassId();
            
            BitSet teacherSlots = conflicts.computeIfAbsent(teacherKey, k -> new BitSet(60));
            BitSet classroomSlots = conflicts.computeIfAbsent(classroomKey, k -> new BitSet(60));
            BitSet classSlots = conflicts.computeIfAbsent(classKey, k -> new BitSet(60));
            
            if (teacherSlots.get(timeSlotIndex)) fitness -= 50;
            if (classroomSlots.get(timeSlotIndex)) fitness -= 50;
            if (classSlots.get(timeSlotIndex)) fitness -= 50;
            
            teacherSlots.set(timeSlotIndex);
            classroomSlots.set(timeSlotIndex);
            classSlots.set(timeSlotIndex);
        }
        
        // 计算其他约束条件的适应度
        fitness += calculateConstraintsFitness(chromosome);
        
        // 缓存计算结果
        redisTemplate.opsForValue().set(cacheKey, fitness, 5, TimeUnit.MINUTES);
        
        return Math.max(0, fitness);
    }
    
    /**
     * 计算约束条件适应度
     */
    private double calculateConstraintsFitness(List<AcLessonSchedule> chromosome) {
        double fitness = 0;
        
        // 从缓存获取约束条件
        Map<String, Object> constraints = new HashMap<>(constraintCache);
        
        // 教师偏好
        fitness += chromosome.stream()
            .mapToInt(AcLessonSchedule::getTeacherPreference)
            .sum() / 10.0;
        
        // 其他约束条件计算...
        
        return fitness;
    }
    
    /**
     * 锦标赛选择
     */
    private List<List<AcLessonSchedule>> tournamentSelection(
            List<List<AcLessonSchedule>> population,
            Map<List<AcLessonSchedule>, Double> fitnessMap) {
        List<List<AcLessonSchedule>> selected = new ArrayList<>();
        Random random = new Random();
        int tournamentSize = 5;
        
        // 保留精英
        int eliteCount = (int) (populationSize * eliteRate);
        List<List<AcLessonSchedule>> sortedPopulation = population.stream()
            .sorted((a, b) -> Double.compare(fitnessMap.get(b), fitnessMap.get(a)))
            .collect(Collectors.toList());
        
        selected.addAll(sortedPopulation.subList(0, eliteCount));
        
        // 锦标赛选择
        while (selected.size() < populationSize) {
            List<List<AcLessonSchedule>> tournament = new ArrayList<>();
            for (int i = 0; i < tournamentSize; i++) {
                tournament.add(population.get(random.nextInt(population.size())));
            }
            
            List<AcLessonSchedule> winner = tournament.stream()
                .max((a, b) -> Double.compare(fitnessMap.get(a), fitnessMap.get(b)))
                .orElse(population.get(0));
            
            selected.add(new ArrayList<>(winner));
        }
        
        return selected;
    }
    
    /**
     * 并行执行交叉和变异
     */
    private List<List<AcLessonSchedule>> crossoverAndMutateParallel(List<List<AcLessonSchedule>> selected) {
        int eliteCount = (int) (selected.size() * eliteRate);
        List<List<AcLessonSchedule>> elites = selected.subList(0, eliteCount);
        
        List<Callable<List<List<AcLessonSchedule>>>> tasks = new ArrayList<>();
        for (int i = eliteCount; i < selected.size() - 1; i += 2) {
            final int index = i;
            tasks.add(() -> crossoverAndMutate(selected.get(index), selected.get(index + 1)));
        }
        
        List<List<AcLessonSchedule>> offspring = new ArrayList<>(elites);
        
        try {
            List<Future<List<List<AcLessonSchedule>>>> futures = executorPool.invokeAll(tasks);
            for (Future<List<List<AcLessonSchedule>>> future : futures) {
                offspring.addAll(future.get());
            }
        } catch (Exception e) {
            // 处理异常
        }
        
        return offspring;
    }
    
    /**
     * 交叉和变异操作
     */
    private List<List<AcLessonSchedule>> crossoverAndMutate(List<AcLessonSchedule> parent1,
                                                         List<AcLessonSchedule> parent2) {
        List<List<AcLessonSchedule>> children = new ArrayList<>();
        Random random = new Random();
        
        if (random.nextDouble() < crossoverRate) {
            // 两点交叉
            int point1 = random.nextInt(parent1.size());
            int point2 = random.nextInt(parent1.size());
            int start = Math.min(point1, point2);
            int end = Math.max(point1, point2);
            
            List<AcLessonSchedule> child1 = new ArrayList<>();
            List<AcLessonSchedule> child2 = new ArrayList<>();
            
            for (int i = 0; i < parent1.size(); i++) {
                if (i >= start && i <= end) {
                    child1.add(cloneSchedule(parent2.get(i)));
                    child2.add(cloneSchedule(parent1.get(i)));
                } else {
                    child1.add(cloneSchedule(parent1.get(i)));
                    child2.add(cloneSchedule(parent2.get(i)));
                }
            }
            
            // 变异
            mutate(child1);
            mutate(child2);
            
            // 修复冲突
            repairScheduleOptimized(child1);
            repairScheduleOptimized(child2);
            
            children.add(child1);
            children.add(child2);
        } else {
            children.add(new ArrayList<>(parent1));
            children.add(new ArrayList<>(parent2));
        }
        
        return children;
    }
    
    /**
     * 变异操作
     */
    private void mutate(List<AcLessonSchedule> chromosome) {
        Random random = new Random();
        
        for (AcLessonSchedule schedule : chromosome) {
            if (random.nextDouble() < mutationRate) {
                // 随机选择变异类型
                switch (random.nextInt(3)) {
                    case 0: // 变异时间
                        schedule.setWeekDay(random.nextInt(5) + 1);
                        schedule.setLessonNo(random.nextInt(12) + 1);
                        break;
                    case 1: // 变异教室
                        List<Long> classrooms = (List<Long>) constraintCache.get("classrooms");
                        if (classrooms != null && !classrooms.isEmpty()) {
                            schedule.setClassroomId(classrooms.get(random.nextInt(classrooms.size())));
                        }
                        break;
                    case 2: // 变异教师
                        List<Long> teachers = (List<Long>) constraintCache.get("teachers");
                        if (teachers != null && !teachers.isEmpty()) {
                            schedule.setTeacherId(teachers.get(random.nextInt(teachers.size())));
                        }
                        break;
                }
            }
        }
    }
    
    /**
     * 优化的冲突修复
     */
    private void repairScheduleOptimized(List<AcLessonSchedule> schedule) {
        Map<String, BitSet> timeSlots = new HashMap<>();
        List<AcLessonSchedule> conflicting = new ArrayList<>();
        
        // 第一遍：标记所有时间槽并收集冲突课程
        for (AcLessonSchedule lesson : schedule) {
            int timeSlotIndex = (lesson.getWeekDay() - 1) * 12 + (lesson.getLessonNo() - 1);
            
            String teacherKey = "T" + lesson.getTeacherId();
            String classroomKey = "R" + lesson.getClassroomId();
            String classKey = "C" + lesson.getClassId();
            
            BitSet teacherSlots = timeSlots.computeIfAbsent(teacherKey, k -> new BitSet(60));
            BitSet classroomSlots = timeSlots.computeIfAbsent(classroomKey, k -> new BitSet(60));
            BitSet classSlots = timeSlots.computeIfAbsent(classKey, k -> new BitSet(60));
            
            if (teacherSlots.get(timeSlotIndex) ||
                classroomSlots.get(timeSlotIndex) ||
                classSlots.get(timeSlotIndex)) {
                conflicting.add(lesson);
            } else {
                teacherSlots.set(timeSlotIndex);
                classroomSlots.set(timeSlotIndex);
                classSlots.set(timeSlotIndex);
            }
        }
        
        // 第二遍：重新安排冲突课程
        Random random = new Random();
        for (AcLessonSchedule lesson : conflicting) {
            boolean resolved = false;
            int attempts = 0;
            
            while (!resolved && attempts < 20) {
                int weekDay = random.nextInt(5) + 1;
                int lessonNo = random.nextInt(12) + 1;
                int timeSlotIndex = (weekDay - 1) * 12 + (lessonNo - 1);
                
                String teacherKey = "T" + lesson.getTeacherId();
                String classroomKey = "R" + lesson.getClassroomId();
                String classKey = "C" + lesson.getClassId();
                
                BitSet teacherSlots = timeSlots.get(teacherKey);
                BitSet classroomSlots = timeSlots.get(classroomKey);
                BitSet classSlots = timeSlots.get(classKey);
                
                if (!teacherSlots.get(timeSlotIndex) &&
                    !classroomSlots.get(timeSlotIndex) &&
                    !classSlots.get(timeSlotIndex)) {
                    
                    lesson.setWeekDay(weekDay);
                    lesson.setLessonNo(lessonNo);
                    
                    teacherSlots.set(timeSlotIndex);
                    classroomSlots.set(timeSlotIndex);
                    classSlots.set(timeSlotIndex);
                    
                    resolved = true;
                }
                
                attempts++;
            }
        }
    }
    
    /**
     * 动态调整算法参数
     */
    private void adjustParameters(int generation, Map<List<AcLessonSchedule>, Double> fitnessMap) {
        double maxFitness = fitnessMap.values().stream().mapToDouble(Double::doubleValue).max().orElse(0);
        double avgFitness = fitnessMap.values().stream().mapToDouble(Double::doubleValue).average().orElse(0);
        
        // 根据种群多样性调整参数
        double diversity = maxFitness - avgFitness;
        
        if (diversity < 50) {
            // 增加变异以提高多样性
            mutationRate = Math.min(0.3, mutationRate * 1.1);
            crossoverRate = Math.max(0.6, crossoverRate * 0.9);
        } else {
            // 减少变异以加快收敛
            mutationRate = Math.max(0.01, mutationRate * 0.9);
            crossoverRate = Math.min(0.9, crossoverRate * 1.1);
        }
        
        // 根据进度调整精英保留比例
        double progress = (double) generation / maxGenerations;
        eliteRate = 0.1 + progress * 0.1; // 随着进度增加精英保留比例
    }
    
    /**
     * 初始化缓存
     */
    private void initializeCache(Map<String, Object> constraints) {
        constraintCache.clear();
        constraintCache.putAll(constraints);
        
        timeSlotCache.clear();
    }
    
    /**
     * 清理缓存
     */
    private void clearCache() {
        constraintCache.clear();
        timeSlotCache.clear();
    }
    
    /**
     * 克隆课程安排
     */
    private AcLessonSchedule cloneSchedule(AcLessonSchedule schedule) {
        AcLessonSchedule clone = new AcLessonSchedule();
        clone.setId(schedule.getId());
        clone.setCourseId(schedule.getCourseId());
        clone.setTeacherId(schedule.getTeacherId());
        clone.setClassroomId(schedule.getClassroomId());
        clone.setClassId(schedule.getClassId());
        clone.setWeekDay(schedule.getWeekDay());
        clone.setLessonNo(schedule.getLessonNo());
        clone.setSemester(schedule.getSemester());
        clone.setTeacherPreference(schedule.getTeacherPreference());
        clone.setStatus(schedule.getStatus());
        return clone;
    }
    
    /**
     * 检查终止条件
     */
    private boolean checkTerminationCondition(Map<List<AcLessonSchedule>, Double> fitnessMap) {
        double maxFitness = fitnessMap.values().stream().mapToDouble(Double::doubleValue).max().orElse(0);
        return maxFitness >= 950;
    }
    
    /**
     * 精英保留策略
     */
    private List<List<AcLessonSchedule>> elitism(List<List<AcLessonSchedule>> oldPopulation,
                                                 List<List<AcLessonSchedule>> newPopulation,
                                                 Map<List<AcLessonSchedule>, Double> fitnessMap) {
        // 计算需要保留的精英数量
        int eliteCount = (int) (populationSize * eliteRate);
        
        // 按适应度排序
        List<Map.Entry<List<AcLessonSchedule>, Double>> sortedFitness = new ArrayList<>(fitnessMap.entrySet());
        sortedFitness.sort(Map.Entry.<List<AcLessonSchedule>, Double>comparingByValue().reversed());
        
        // 创建新种群
        List<List<AcLessonSchedule>> result = new ArrayList<>();
        
        // 添加精英
        for (int i = 0; i < eliteCount && i < sortedFitness.size(); i++) {
            result.add(new ArrayList<>(sortedFitness.get(i).getKey()));
        }
        
        // 添加新一代个体
        for (int i = 0; i < populationSize - eliteCount && i < newPopulation.size(); i++) {
            result.add(newPopulation.get(i));
        }
        
        return result;
    }
    
    /**
     * 获取最优解
     */
    private List<AcLessonSchedule> getBestSolution(List<List<AcLessonSchedule>> population) {
        return population.stream()
            .max((a, b) -> Double.compare(
                calculateFitnessOptimized(a),
                calculateFitnessOptimized(b)
            ))
            .orElse(new ArrayList<>());
    }
}